package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
* 题目描述：
* 给定一个无重复元素的数组 candidates 和一个目标数 target 
* ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 组合总和_39 {
    public static void main(String[] args) {
        组合总和_39 demo = new 组合总和_39();
        List<List<Integer>> realResult = demo.combinationSum(
                new int[]{
                        2,3,5
                },8
        );
        for(List<Integer> temp : realResult){
            System.out.println(temp.toString());
        }
    }
    /*
    * 他的这个不重复组合的解法 可以参考三数之和 和 四数之和
    * a+b+c+...+n = target 只要保证 每次加上去的那个数 都 >= 前一个加上去的数即可
    * 这样子应该就不会有重复的组合了 (好像不需要。。。 因为数组中的元素是不重复的)
    * 总体就是 搜索+回溯+剪枝
    * */
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        ArrayList<Integer> nowList = new ArrayList<>();
        int now = 0;
        f(candidates,0,now,target,nowList);
        return result;
    }
    public void f(int[] nums,int index,int now,int target,ArrayList<Integer> nowList){
        // 加上当前数还是小于
        for(int i=index;i<nums.length;i++){
            if(now+nums[i]<target){
                nowList.add(nums[i]);
                f(nums,i,now+nums[i],target,nowList);
                // 回溯
                nowList.remove(nowList.size()-1);
            }else if(now+nums[i]>target){
                // 直接回溯
                return ;
            }else{
                // 相等
                nowList.add(nums[i]);
                result.add((List<Integer>)nowList.clone());
                nowList.remove(nowList.size()-1);
                return ;
            }
        }
    }
}
